package com.peng.leetcode.tree;

/**
 * IncreasingBST1
 * 897. 递增顺序搜索树
 * https://leetcode.cn/problems/increasing-order-search-tree/
 * <p>
 * Created on 2022/12/7
 *
 * @author lupeng
 */
public class IncreasingBST1 {
    public TreeNode increasingBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        dfs(root);
        return head;
    }

    TreeNode head = null;
    TreeNode pre = null;

    void dfs(TreeNode n) {
        if (n == null) {
            return;
        }
        dfs(n.left);
        if (pre == null) {
            head = n;
        } else {
            pre.right = n;
        }
        n.left = null;
        pre = n;
        dfs(n.right);
    }
}
